home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / gxccman.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  24.7 KB  |  801 lines
  1. /* Copyright (C) 1989, 1995, 1996, 1997, 1999 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: gxccman.c,v 1.2 2000/09/19 19:00:33 lpd Exp $ */
  20. /* Character cache management routines for Ghostscript library */
  21. #include "gx.h"
  22. #include "memory_.h"
  23. #include "gpcheck.h"
  24. #include "gserrors.h"
  25. #include "gsstruct.h"
  26. #include "gsbitops.h"
  27. #include "gsutil.h"        /* for gs_next_ids */
  28. #include "gxfixed.h"
  29. #include "gxmatrix.h"
  30. #include "gzstate.h"
  31. #include "gxpath.h"
  32. #include "gxdevice.h"
  33. #include "gxdevmem.h"
  34. #include "gxchar.h"
  35. #include "gxfont.h"
  36. #include "gxfcache.h"
  37. #include "gxxfont.h"
  38.  
  39. /* Define the descriptors for the cache structures. */
  40. private_st_cached_fm_pair();
  41. private_st_cached_fm_pair_elt();
  42. /*private_st_cached_char(); *//* unused */
  43. private_st_cached_char_ptr();    /* unused */
  44. private_st_cached_char_ptr_elt();
  45. /*
  46.  * Define a descriptor for the cache data.  This is equivalent to st_bytes,
  47.  * but it identifies the cache data as such in a memory dump.
  48.  */
  49. gs_private_st_simple(st_font_cache_bytes, byte, "font cache bytes");
  50. /* GC procedures */
  51. /* We do all the work in font_dir_enum/reloc_ptrs in gsfont.c. */
  52. /* See gxfcache.h for details. */
  53. private 
  54. ENUM_PTRS_BEGIN(cc_ptr_enum_ptrs) return 0;
  55.  
  56. ENUM_PTRS_END
  57. private RELOC_PTRS_BEGIN(cc_ptr_reloc_ptrs)
  58. {
  59. }
  60. RELOC_PTRS_END
  61.  
  62. /* Forward references */
  63. private gx_xfont * lookup_xfont_by_name(P6(gx_device *, const gx_xfont_procs *, gs_font_name *, int, const cached_fm_pair *, const gs_matrix *));
  64. private cached_char *alloc_char(P2(gs_font_dir *, ulong));
  65. private cached_char *alloc_char_in_chunk(P2(gs_font_dir *, ulong));
  66. private void hash_remove_cached_char(P2(gs_font_dir *, uint));
  67. private void shorten_cached_char(P3(gs_font_dir *, cached_char *, uint));
  68.  
  69. /* ====== Initialization ====== */
  70.  
  71. /* Allocate and initialize the character cache elements of a font directory. */
  72. int
  73. gx_char_cache_alloc(gs_memory_t * struct_mem, gs_memory_t * bits_mem,
  74.         gs_font_dir * pdir, uint bmax, uint mmax, uint cmax, uint upper)
  75. {                /* Since we use open hashing, we must increase cmax somewhat. */
  76.     uint chsize = (cmax + (cmax >> 1)) | 31;
  77.     cached_fm_pair *mdata;
  78.     cached_char **chars;
  79.  
  80.     /* Round up chsize to a power of 2. */
  81.     while (chsize & (chsize + 1))
  82.     chsize |= chsize >> 1;
  83.     chsize++;
  84.     mdata = gs_alloc_struct_array(struct_mem, mmax, cached_fm_pair,
  85.                   &st_cached_fm_pair_element,
  86.                   "font_dir_alloc(mdata)");
  87.     chars = gs_alloc_struct_array(struct_mem, chsize, cached_char *,
  88.                   &st_cached_char_ptr_element,
  89.                   "font_dir_alloc(chars)");
  90.     if (mdata == 0 || chars == 0) {
  91.     gs_free_object(struct_mem, chars, "font_dir_alloc(chars)");
  92.     gs_free_object(struct_mem, mdata, "font_dir_alloc(mdata)");
  93.     return_error(gs_error_VMerror);
  94.     }
  95.     pdir->fmcache.mmax = mmax;
  96.     pdir->fmcache.mdata = mdata;
  97.     pdir->ccache.struct_memory = struct_mem;
  98.     pdir->ccache.bits_memory = bits_mem;
  99.     pdir->ccache.bmax = bmax;
  100.     pdir->ccache.cmax = cmax;
  101.     pdir->ccache.lower = upper / 10;
  102.     pdir->ccache.upper = upper;
  103.     pdir->ccache.table = chars;
  104.     pdir->ccache.table_mask = chsize - 1;
  105.     gx_char_cache_init(pdir);
  106.     return 0;
  107. }
  108.  
  109. /* Initialize the character cache. */
  110. void
  111. gx_char_cache_init(register gs_font_dir * dir)
  112. {
  113.     int i;
  114.     cached_fm_pair *pair;
  115.     char_cache_chunk *cck = (char_cache_chunk *)
  116.     gs_alloc_bytes_immovable(dir->ccache.bits_memory,
  117.                  sizeof(char_cache_chunk),
  118.                  "initial_chunk");
  119.  
  120.     dir->fmcache.msize = 0;
  121.     dir->fmcache.mnext = 0;
  122.     gx_bits_cache_chunk_init(cck, NULL, 0);
  123.     gx_bits_cache_init((gx_bits_cache *) & dir->ccache, cck);
  124.     dir->ccache.bspace = 0;
  125.     memset((char *)dir->ccache.table, 0,
  126.        (dir->ccache.table_mask + 1) * sizeof(cached_char *));
  127.     for (i = 0, pair = dir->fmcache.mdata;
  128.      i < dir->fmcache.mmax; i++, pair++
  129.     ) {
  130.     pair->index = i;
  131.     fm_pair_init(pair);
  132.     }
  133. }
  134.  
  135. /* ====== Purging ====== */
  136.  
  137. /* Purge from the character cache all entries selected by */
  138. /* a client-supplied procedure. */
  139. void
  140. gx_purge_selected_cached_chars(gs_font_dir * dir,
  141.            bool(*proc) (P2(cached_char *, void *)), void *proc_data)
  142. {
  143.     int chi;
  144.     int cmax = dir->ccache.table_mask;
  145.  
  146.     for (chi = 0; chi <= cmax;) {
  147.     cached_char *cc = dir->ccache.table[chi];
  148.  
  149.     if (cc != 0 && (*proc) (cc, proc_data)) {
  150.         hash_remove_cached_char(dir, chi);
  151.         gx_free_cached_char(dir, cc);
  152.     } else
  153.         chi++;
  154.     }
  155. }
  156.  
  157. /* ====== Font-level routines ====== */
  158.  
  159. /* Add a font/matrix pair to the cache. */
  160. /* (This is only exported for gxccache.c.) */
  161. cached_fm_pair *
  162. gx_add_fm_pair(register gs_font_dir * dir, gs_font * font, const gs_uid * puid,
  163.            const gs_state * pgs)
  164. {
  165.     register cached_fm_pair *pair =
  166.     dir->fmcache.mdata + dir->fmcache.mnext;
  167.     cached_fm_pair *mend =
  168.     dir->fmcache.mdata + dir->fmcache.mmax;
  169.  
  170.     if (dir->fmcache.msize == dir->fmcache.mmax) {    /* cache is full *//* Prefer an entry with num_chars == 0, if any. */
  171.     int count;
  172.  
  173.     for (count = dir->fmcache.mmax;
  174.          --count >= 0 && pair->num_chars != 0;
  175.         )
  176.         if (++pair == mend)
  177.         pair = dir->fmcache.mdata;
  178.     gs_purge_fm_pair(dir, pair, 0);
  179.     } else {            /* Look for an empty entry.  (We know there is one.) */
  180.     while (!fm_pair_is_free(pair))
  181.         if (++pair == mend)
  182.         pair = dir->fmcache.mdata;
  183.     }
  184.     dir->fmcache.msize++;
  185.     dir->fmcache.mnext = pair + 1 - dir->fmcache.mdata;
  186.     if (dir->fmcache.mnext == dir->fmcache.mmax)
  187.     dir->fmcache.mnext = 0;
  188.     pair->font = font;
  189.     pair->UID = *puid;
  190.     pair->FontType = font->FontType;
  191.     /* The OSF/1 compiler doesn't like casting a pointer to */
  192.     /* a shorter int.... */
  193.     pair->hash = (uint) (ulong) pair % 549;    /* scramble bits */
  194.     pair->mxx = pgs->char_tm.xx, pair->mxy = pgs->char_tm.xy;
  195.     pair->myx = pgs->char_tm.yx, pair->myy = pgs->char_tm.yy;
  196.     pair->num_chars = 0;
  197.     pair->xfont_tried = false;
  198.     pair->xfont = 0;
  199.     if_debug8('k', "[k]adding pair 0x%lx: font=0x%lx [%g %g %g %g] UID %ld, 0x%lx\n",
  200.           (ulong) pair, (ulong) font,
  201.           pair->mxx, pair->mxy, pair->myx, pair->myy,
  202.           (long)pair->UID.id, (ulong) pair->UID.xvalues);
  203.     return pair;
  204. }
  205.  
  206. /* Look up the xfont for a font/matrix pair. */
  207. /* (This is only exported for gxccache.c.) */
  208. void
  209. gx_lookup_xfont(const gs_state * pgs, cached_fm_pair * pair, int encoding_index)
  210. {
  211.     gx_device *dev = gs_currentdevice(pgs);
  212.     gx_device *fdev = (*dev_proc(dev, get_xfont_device)) (dev);
  213.     gs_font *font = pair->font;
  214.     const gx_xfont_procs *procs = (*dev_proc(fdev, get_xfont_procs)) (fdev);
  215.     gx_xfont *xf = 0;
  216.  
  217.     /* We mustn't attempt to use xfonts for stroked characters, */
  218.     /* because such characters go outside their bounding box. */
  219.     if (procs != 0 && font->PaintType == 0) {
  220.     gs_matrix mat;
  221.  
  222.     mat.xx = pair->mxx, mat.xy = pair->mxy;
  223.     mat.yx = pair->myx, mat.yy = pair->myy;
  224.     mat.tx = 0, mat.ty = 0;
  225.     /* xfonts can outlive their invocations, */
  226.     /* but restore purges them properly. */
  227.     pair->memory = pgs->memory;
  228.     if (font->key_name.size != 0)
  229.         xf = lookup_xfont_by_name(fdev, procs,
  230.                       &font->key_name, encoding_index,
  231.                       pair, &mat);
  232. #define font_name_eq(pfn1,pfn2)\
  233.   ((pfn1)->size == (pfn2)->size && (pfn1)->size != 0 &&\
  234.    !memcmp((char *)(pfn1)->chars, (char *)(pfn2)->chars, (pfn1)->size))
  235.     if (xf == 0 && font->font_name.size != 0 &&
  236.     /* Avoid redundant lookup */
  237.         !font_name_eq(&font->font_name, &font->key_name)
  238.         )
  239.         xf = lookup_xfont_by_name(fdev, procs,
  240.                       &font->font_name, encoding_index,
  241.                       pair, &mat);
  242.     if (xf == 0 && font->FontType != ft_composite &&
  243.         uid_is_valid(&((gs_font_base *) font)->UID)
  244.         ) {            /* Look for an original font with the same UID. */
  245.         gs_font_dir *pdir = font->dir;
  246.         gs_font *pfont;
  247.  
  248.         for (pfont = pdir->orig_fonts; pfont != 0;
  249.          pfont = pfont->next
  250.         ) {
  251.         if (pfont->FontType != ft_composite &&
  252.             uid_equal(&((gs_font_base *) pfont)->UID,
  253.                   &((gs_font_base *) font)->UID) &&
  254.             pfont->key_name.size != 0 &&
  255.             !font_name_eq(&font->key_name,
  256.                   &pfont->key_name)
  257.             ) {
  258.             xf = lookup_xfont_by_name(fdev, procs,
  259.                           &pfont->key_name,
  260.                           encoding_index, pair, &mat);
  261.             if (xf != 0)
  262.             break;
  263.         }
  264.         }
  265.     }
  266.     }
  267.     pair->xfont = xf;
  268. }
  269.  
  270. /* ------ Internal routines ------ */
  271.  
  272. /* Purge from the caches all references to a given font/matrix pair, */
  273. /* or just characters that depend on its xfont. */
  274. #define cpair ((cached_fm_pair *)vpair)
  275. private bool
  276. purge_fm_pair_char(cached_char * cc, void *vpair)
  277. {
  278.     return cc_pair(cc) == cpair;
  279. }
  280. private bool
  281. purge_fm_pair_char_xfont(cached_char * cc, void *vpair)
  282. {
  283.     return cc_pair(cc) == cpair && cpair->xfont == 0 && !cc_has_bits(cc);
  284. }
  285. #undef cpair
  286. void
  287. gs_purge_fm_pair(gs_font_dir * dir, cached_fm_pair * pair, int xfont_only)
  288. {
  289.     if_debug2('k', "[k]purging pair 0x%lx%s\n",
  290.           (ulong) pair, (xfont_only ? " (xfont only)" : ""));
  291.     if (pair->xfont != 0) {
  292.     (*pair->xfont->common.procs->release) (pair->xfont,
  293.                            pair->memory);
  294.     pair->xfont_tried = false;
  295.     pair->xfont = 0;
  296.     }
  297.     gx_purge_selected_cached_chars(dir,
  298.                    (xfont_only ? purge_fm_pair_char_xfont :
  299.                     purge_fm_pair_char),
  300.                    pair);
  301.     if (!xfont_only) {
  302. #ifdef DEBUG
  303.     if (pair->num_chars != 0) {
  304.         lprintf1("Error in gs_purge_fm_pair: num_chars =%d\n",
  305.              pair->num_chars);
  306.     }
  307. #endif
  308.     fm_pair_set_free(pair);
  309.     dir->fmcache.msize--;
  310.     }
  311. }
  312.  
  313. /* Look up an xfont by name. */
  314. /* The caller must already have done get_xfont_device to get the proper */
  315. /* device to pass as the first argument to lookup_font. */
  316. private gx_xfont *
  317. lookup_xfont_by_name(gx_device * fdev, const gx_xfont_procs * procs,
  318.       gs_font_name * pfstr, int encoding_index, const cached_fm_pair * pair,
  319.              const gs_matrix * pmat)
  320. {
  321.     gx_xfont *xf;
  322.  
  323.     if_debug5('k', "[k]lookup xfont %s [%g %g %g %g]\n",
  324.           pfstr->chars, pmat->xx, pmat->xy, pmat->yx, pmat->yy);
  325.     xf = (*procs->lookup_font) (fdev,
  326.                 &pfstr->chars[0], pfstr->size,
  327.                 encoding_index, &pair->UID,
  328.                 pmat, pair->memory);
  329.     if_debug1('k', "[k]... xfont=0x%lx\n", (ulong) xf);
  330.     return xf;
  331. }
  332.  
  333. /* ====== Character-level routines ====== */
  334.  
  335. /*
  336.  * Allocate storage for caching a rendered character with possible
  337.  * oversampling and/or alpha.  Return the cached_char if OK, 0 if too big.
  338.  * If the character is being oversampled, make the size decision
  339.  * on the basis of the final (scaled-down) size.
  340.  *
  341.  * The iwidth and iheight parameters include scaling up for oversampling
  342.  * (multiplication by 1 << pscale->{x,y}.)
  343.  * The depth parameter is the final number of alpha bits;
  344.  * depth <= x scale * y scale.
  345.  * If dev == NULL, this is an xfont-only entry.
  346.  * If dev != NULL, set up the memory device(s); in this case, if dev2 is
  347.  * not NULL, dev should be an alpha-buffer device with dev2 (an alpha
  348.  * device) as target.
  349.  */
  350. cached_char *
  351. gx_alloc_char_bits(gs_font_dir * dir, gx_device_memory * dev,
  352.            gx_device_memory * dev2, ushort iwidth, ushort iheight,
  353.            const gs_log2_scale_point * pscale, int depth)
  354. {
  355.     int log2_xscale = pscale->x;
  356.     int log2_yscale = pscale->y;
  357.     int log2_depth = ilog2(depth);
  358.     uint nwidth_bits = (iwidth >> log2_xscale) << log2_depth;
  359.     ulong isize, icdsize;
  360.     uint iraster;
  361.     cached_char *cc;
  362.     gx_device_memory mdev;
  363.     gx_device_memory *pdev = dev;
  364.     gx_device_memory *pdev2;
  365.  
  366.     if (dev == NULL) {
  367.     mdev.memory = 0;
  368.     mdev.target = 0;
  369.     pdev = &mdev;
  370.     }
  371.     pdev2 = (dev2 == 0 ? pdev : dev2);
  372.  
  373.     /* Compute the scaled-down bitmap size, and test against */
  374.     /* the maximum cachable character size. */
  375.  
  376.     iraster = bitmap_raster(nwidth_bits);
  377.     if (iraster != 0 && iheight >> log2_yscale > dir->ccache.upper / iraster) {
  378.     if_debug5('k', "[k]no cache bits: scale=%dx%d, raster/scale=%u, height/scale=%u, upper=%u\n",
  379.           1 << log2_xscale, 1 << log2_yscale,
  380.           iraster, iheight, dir->ccache.upper);
  381.     return 0;        /* too big */
  382.     }
  383.     /* Compute the actual bitmap size(s) and allocate the bits. */
  384.     if (dev2 == 0) {
  385.     /*
  386.      * Render to a full (possibly oversampled) bitmap; compress
  387.      * (if needed) when done.
  388.      *
  389.      * HACK: Preserve the reference count and retained flag.
  390.      */
  391.     rc_header rc;
  392.     bool retained = pdev->retained;
  393.     gx_device *target = pdev->target;
  394.  
  395.     rc = pdev->rc;
  396.     /* Pass the correct target, but decrement its refct afterwards. */
  397.     gs_make_mem_mono_device(pdev, pdev->memory, target);
  398.     rc_decrement_only(target, "gx_alloc_char_bits"); /* can't go to 0 */
  399.     pdev->rc = rc;
  400.     pdev->retained = retained;
  401.     pdev->width = iwidth;
  402.     pdev->height = iheight;
  403.     isize = gdev_mem_bitmap_size(pdev);
  404.     } else {
  405.     /* Use an alpha-buffer device to compress as we go. */
  406.     /* Preserve the reference counts, if any. */
  407.     rc_header rc;
  408.  
  409.     rc = dev2->rc;
  410.     gs_make_mem_alpha_device(dev2, dev2->memory, NULL, depth);
  411.     dev2->rc = rc;
  412.     dev2->width = iwidth >> log2_xscale;
  413.     dev2->height = iheight >> log2_yscale;
  414.     rc = dev->rc;
  415.     gs_make_mem_abuf_device(dev, dev->memory, (gx_device *) dev2,
  416.                 pscale, depth, 0);
  417.     dev->rc = rc;
  418.     dev->width = iwidth;
  419.     dev->height = 2 << log2_yscale;
  420.     isize = gdev_mem_bitmap_size(dev) +
  421.         gdev_mem_bitmap_size(dev2);
  422.     }
  423.     icdsize = isize + sizeof_cached_char;
  424.     cc = alloc_char(dir, icdsize);
  425.     if (cc == 0)
  426.     return 0;
  427.     if_debug4('k', "[k]adding char 0x%lx:%u(%u,%u)\n",
  428.           (ulong) cc, (uint) icdsize, iwidth, iheight);
  429.  
  430.     /* Fill in the entry. */
  431.  
  432.     cc_set_depth(cc, depth);
  433.     cc->xglyph = gx_no_xglyph;
  434.     /* Set the width and height to those of the device. */
  435.     /* Note that if we are oversampling without an alpha buffer. */
  436.     /* these are not the final unscaled dimensions. */
  437.     cc->width = pdev2->width;
  438.     cc->height = pdev2->height;
  439.     cc->shift = 0;
  440.     cc_set_raster(cc, gdev_mem_raster(pdev2));
  441.     cc_set_pair_only(cc, 0);    /* not linked in yet */
  442.     cc->id = gx_no_bitmap_id;
  443.  
  444.     /* Open the cache device(s). */
  445.  
  446.     if (dev2) {            /* The second device is an alpha device that targets */
  447.     /* the real storage for the character. */
  448.     byte *bits = cc_bits(cc);
  449.     uint bsize = (uint) gdev_mem_bitmap_size(dev2);
  450.  
  451.     memset(bits, 0, bsize);
  452.     dev2->base = bits;
  453.     (*dev_proc(dev2, open_device)) ((gx_device *) dev2);
  454.     dev->base = bits + bsize;
  455.     (*dev_proc(dev, open_device)) ((gx_device *) dev);
  456.     } else if (dev)
  457.     gx_open_cache_device(dev, cc);
  458.  
  459.     return cc;
  460. }
  461.  
  462. /* Open the cache device. */
  463. void
  464. gx_open_cache_device(gx_device_memory * dev, cached_char * cc)
  465. {
  466.     byte *bits = cc_bits(cc);
  467.  
  468.     dev->width = cc->width;
  469.     dev->height = cc->height;
  470.     memset((char *)bits, 0, (uint) gdev_mem_bitmap_size(dev));
  471.     dev->base = bits;
  472.     (*dev_proc(dev, open_device)) ((gx_device *) dev);    /* initialize */
  473. }
  474.  
  475. /* Remove a character from the cache. */
  476. void
  477. gx_free_cached_char(gs_font_dir * dir, cached_char * cc)
  478. {
  479.     char_cache_chunk *cck = cc->chunk;
  480.  
  481.     dir->ccache.chunks = cck;
  482.     dir->ccache.cnext = (byte *) cc - cck->data;
  483.     if (cc_pair(cc) != 0) {    /* might be allocated but not added to table yet */
  484.     cc_pair(cc)->num_chars--;
  485.     }
  486.     if_debug2('k', "[k]freeing char 0x%lx, pair=0x%lx\n",
  487.           (ulong) cc, (ulong) cc_pair(cc));
  488.     gx_bits_cache_free((gx_bits_cache *) & dir->ccache, &cc->head, cck);
  489. }
  490.  
  491. /* Add a character to the cache */
  492. void
  493. gx_add_cached_char(gs_font_dir * dir, gx_device_memory * dev,
  494. cached_char * cc, cached_fm_pair * pair, const gs_log2_scale_point * pscale)
  495. {
  496.     if_debug5('k', "[k]chaining char 0x%lx: pair=0x%lx, glyph=0x%lx, wmode=%d, depth=%d\n",
  497.           (ulong) cc, (ulong) pair, (ulong) cc->code,
  498.           cc->wmode, cc_depth(cc));
  499.     if (dev != NULL) {
  500.     static const gs_log2_scale_point no_scale =
  501.     {0, 0};
  502.  
  503.     /* Close the device, to flush the alpha buffer if any. */
  504.     (*dev_proc(dev, close_device)) ((gx_device *) dev);
  505.     gx_add_char_bits(dir, cc,
  506.              (gs_device_is_abuf((gx_device *) dev) ?
  507.               &no_scale : pscale));
  508.     }
  509.     /* Add the new character to the hash table. */
  510.     {
  511.     uint chi = chars_head_index(cc->code, pair);
  512.  
  513.     while (dir->ccache.table[chi &= dir->ccache.table_mask] != 0)
  514.         chi++;
  515.     dir->ccache.table[chi] = cc;
  516.     cc_set_pair(cc, pair);
  517.     pair->num_chars++;
  518.     }
  519. }
  520.  
  521. /* Adjust the bits of a newly-rendered character, by unscaling */
  522. /* and compressing or converting to alpha values if necessary. */
  523. void
  524. gx_add_char_bits(gs_font_dir * dir, cached_char * cc,
  525.          const gs_log2_scale_point * plog2_scale)
  526. {
  527.     int log2_x = plog2_scale->x, log2_y = plog2_scale->y;
  528.     uint raster = cc_raster(cc);
  529.     byte *bits = cc_bits(cc);
  530.     int depth = cc_depth(cc);
  531.     int log2_depth = ilog2(depth);
  532.     uint nwidth_bits, nraster;
  533.     gs_int_rect bbox;
  534.  
  535. #ifdef DEBUG
  536.     if (cc->width % (1 << log2_x) != 0 ||
  537.     cc->height % (1 << log2_y) != 0
  538.     ) {
  539.     lprintf4("size %d,%d not multiple of scale %d,%d!\n",
  540.          cc->width, cc->height,
  541.          1 << log2_x, 1 << log2_y);
  542.     cc->width &= -1 << log2_x;
  543.     cc->height &= -1 << log2_y;
  544.     }
  545. #endif
  546.  
  547.     /*
  548.      * Compute the bounding box before compressing.
  549.      * We may have to scan more bits, but this is a lot faster than
  550.      * compressing the white space.  Note that all bbox values are
  551.      * in bits, not pixels.
  552.      */
  553.  
  554.     bits_bounding_box(bits, cc->height, raster, &bbox);
  555.  
  556.     /*
  557.      * If the character was oversampled, compress it now.
  558.      * In this case we know that log2_depth <= log2_x.
  559.      * If the character was not oversampled, or if we converted
  560.      * oversampling to alpha dynamically (using an alpha buffer
  561.      * intermediate device), log2_x and log2_y are both zero,
  562.      * but in the latter case we may still have depth > 1.
  563.      */
  564.  
  565.     if ((log2_x | log2_y) != 0) {
  566.     if_debug5('k', "[k]compressing %dx%d by %dx%d to depth=%d\n",
  567.           cc->width, cc->height, 1 << log2_x, 1 << log2_y,
  568.           depth);
  569.     if (gs_debug_c('K'))
  570.         debug_dump_bitmap(bits, raster, cc->height,
  571.                   "[K]uncompressed bits");
  572.     /* Truncate/round the bbox to a multiple of the scale. */
  573.     {
  574.         int scale_x = 1 << log2_x;
  575.  
  576.         bbox.p.x &= -scale_x;
  577.         bbox.q.x = (bbox.q.x + scale_x - 1) & -scale_x;
  578.     }
  579.     {
  580.         int scale_y = 1 << log2_y;
  581.  
  582.         bbox.p.y &= -scale_y;
  583.         bbox.q.y = (bbox.q.y + scale_y - 1) & -scale_y;
  584.     }
  585.     cc->width = (bbox.q.x - bbox.p.x) >> log2_x;
  586.     cc->height = (bbox.q.y - bbox.p.y) >> log2_y;
  587.     nwidth_bits = cc->width << log2_depth;
  588.     nraster = bitmap_raster(nwidth_bits);
  589.     bits_compress_scaled(bits + raster * bbox.p.y, bbox.p.x,
  590.                  cc->width << log2_x,
  591.                  cc->height << log2_y,
  592.                  raster,
  593.                  bits, nraster, plog2_scale, log2_depth);
  594.     bbox.p.x >>= log2_x;
  595.     bbox.p.y >>= log2_y;
  596.     } else {
  597.     /* No oversampling, just remove white space on all 4 sides. */
  598.     const byte *from = bits + raster * bbox.p.y + (bbox.p.x >> 3);
  599.  
  600.     cc->height = bbox.q.y - bbox.p.y;
  601.     bbox.p.x &= ~7;        /* adjust to byte boundary */
  602.     bbox.p.x >>= log2_depth;    /* bits => pixels */
  603.     bbox.q.x = (bbox.q.x + depth - 1) >> log2_depth;    /* ditto */
  604.     cc->width = bbox.q.x - bbox.p.x;
  605.     nwidth_bits = cc->width << log2_depth;
  606.     nraster = bitmap_raster(nwidth_bits);
  607.     if (bbox.p.x != 0 || nraster != raster) {
  608.         /* Move the bits down and over. */
  609.         byte *to = bits;
  610.         uint n = cc->height;
  611.  
  612.         /* We'd like to move only 
  613.            uint nbytes = (nwidth_bits + 7) >> 3;
  614.            * bytes per scan line, but unfortunately this drops
  615.            * the guaranteed zero padding at the end.
  616.          */
  617.  
  618.         for (; n--; from += raster, to += nraster)
  619.         memmove(to, from, /*nbytes */ nraster);
  620.     } else if (bbox.p.y != 0) {    /* Just move the bits down. */
  621.         memmove(bits, from, raster * cc->height);
  622.     }
  623.     }
  624.  
  625.     /* Adjust the offsets to account for removed white space. */
  626.  
  627.     cc->offset.x -= int2fixed(bbox.p.x);
  628.     cc->offset.y -= int2fixed(bbox.p.y);
  629.  
  630.     /* Discard the memory device overhead that follows the bits, */
  631.     /* and any space reclaimed from unscaling or compression. */
  632.  
  633.     cc_set_raster(cc, nraster);
  634.     {
  635.     uint diff = ROUND_DOWN(cc->head.size - sizeof_cached_char -
  636.                    nraster * cc->height,
  637.                    align_cached_char_mod);
  638.  
  639.     if (diff >= sizeof(cached_char_head)) {
  640.         shorten_cached_char(dir, cc, diff);
  641.         if_debug2('K', "[K]shortening char 0x%lx by %u (adding)\n",
  642.               (ulong) cc, diff);
  643.     }
  644.     }
  645.  
  646.     /* Assign a bitmap id. */
  647.  
  648.     cc->id = gs_next_ids(1);
  649. }
  650.  
  651. /* Purge from the caches all references to a given font. */
  652. void
  653. gs_purge_font_from_char_caches(gs_font_dir * dir, const gs_font * font)
  654. {
  655.     cached_fm_pair *pair = dir->fmcache.mdata;
  656.     int count = dir->fmcache.mmax;
  657.  
  658.     if_debug1('k', "[k]purging font 0x%lx\n",
  659.           (ulong) font);
  660.     while (count--) {
  661.     if (pair->font == font) {
  662.         if (uid_is_valid(&pair->UID)) {    /* Keep the entry. */
  663.         pair->font = 0;
  664.         } else
  665.         gs_purge_fm_pair(dir, pair, 0);
  666.     }
  667.     pair++;
  668.     }
  669. }
  670.  
  671. /* ------ Internal routines ------ */
  672.  
  673. /* Allocate data space for a cached character, adding a new chunk if needed. */
  674. private cached_char *
  675. alloc_char(gs_font_dir * dir, ulong icdsize)
  676. {                /* Try allocating at the current position first. */
  677.     cached_char *cc = alloc_char_in_chunk(dir, icdsize);
  678.  
  679.     if (cc == 0) {
  680.     if (dir->ccache.bspace < dir->ccache.bmax) {    /* Allocate another chunk. */
  681.         gs_memory_t *mem = dir->ccache.bits_memory;
  682.         char_cache_chunk *cck_prev = dir->ccache.chunks;
  683.         char_cache_chunk *cck;
  684.         uint cksize = dir->ccache.bmax / 5 + 1;
  685.         uint tsize = dir->ccache.bmax - dir->ccache.bspace;
  686.         byte *cdata;
  687.  
  688.         if (cksize > tsize)
  689.         cksize = tsize;
  690.         if (icdsize + sizeof(cached_char_head) > cksize) {
  691.         if_debug2('k', "[k]no cache bits: cdsize+head=%lu, cksize=%u\n",
  692.               icdsize + sizeof(cached_char_head),
  693.               cksize);
  694.         return 0;    /* wouldn't fit */
  695.         }
  696.         cck = (char_cache_chunk *)
  697.         gs_alloc_bytes_immovable(mem, sizeof(*cck),
  698.                      "char cache chunk");
  699.         if (cck == 0)
  700.         return 0;
  701.         cdata =
  702.         gs_alloc_struct_array_immovable(mem, cksize, byte,
  703.                         &st_font_cache_bytes,
  704.                         "char cache chunk(data)");
  705.         if (cdata == 0) {
  706.         gs_free_object(mem, cck, "char cache chunk");
  707.         return 0;
  708.         }
  709.         gx_bits_cache_chunk_init(cck, cdata, cksize);
  710.         cck->next = cck_prev->next;
  711.         cck_prev->next = cck;
  712.         dir->ccache.bspace += cksize;
  713.         dir->ccache.chunks = cck;
  714.     } else {        /* Cycle through existing chunks. */
  715.         char_cache_chunk *cck_init = dir->ccache.chunks;
  716.         char_cache_chunk *cck = cck_init;
  717.  
  718.         while ((dir->ccache.chunks = cck = cck->next) != cck_init) {
  719.         dir->ccache.cnext = 0;
  720.         cc = alloc_char_in_chunk(dir, icdsize);
  721.         if (cc != 0)
  722.             return cc;
  723.         }
  724.     }
  725.     dir->ccache.cnext = 0;
  726.     cc = alloc_char_in_chunk(dir, icdsize);
  727.     }
  728.     return cc;
  729. }
  730.  
  731. /* Allocate a character in the current chunk. */
  732. private cached_char *
  733. alloc_char_in_chunk(gs_font_dir * dir, ulong icdsize)
  734. {
  735.     char_cache_chunk *cck = dir->ccache.chunks;
  736.     cached_char_head *cch;
  737.  
  738. #define cc ((cached_char *)cch)
  739.  
  740.     while (gx_bits_cache_alloc((gx_bits_cache *) & dir->ccache,
  741.                    icdsize, &cch) < 0
  742.     ) {
  743.     if (cch == 0) {        /* Not enough room to allocate in this chunk. */
  744.         return 0;
  745.     } {            /* Free the character */
  746.         cached_fm_pair *pair = cc_pair(cc);
  747.  
  748.         if (pair != 0) {
  749.         uint chi = chars_head_index(cc->code, pair);
  750.  
  751.         while (dir->ccache.table[chi & dir->ccache.table_mask] != cc)
  752.             chi++;
  753.         hash_remove_cached_char(dir, chi);
  754.         }
  755.         gx_free_cached_char(dir, cc);
  756.     }
  757.     }
  758.     cc->chunk = cck;
  759.     cc->loc = (byte *) cc - cck->data;
  760.     return cc;
  761. #undef cc
  762. }
  763.  
  764. /* Remove the cached_char at a given index in the hash table. */
  765. /* In order not to slow down lookup, we relocate following entries. */
  766. private void
  767. hash_remove_cached_char(gs_font_dir * dir, uint chi)
  768. {
  769.     uint mask = dir->ccache.table_mask;
  770.     uint from = ((chi &= mask) + 1) & mask;
  771.     cached_char *cc;
  772.  
  773.     dir->ccache.table[chi] = 0;
  774.     while ((cc = dir->ccache.table[from]) != 0) {    /* Loop invariants: chars[chi] == 0; */
  775.     /* chars[chi+1..from] != 0. */
  776.     uint fchi = chars_head_index(cc->code, cc_pair(cc));
  777.  
  778.     /* If chi <= fchi < from, we relocate the character. */
  779.     /* Note that '<=' must take wraparound into account. */
  780.     if ((chi < from ? chi <= fchi && fchi < from :
  781.          chi <= fchi || fchi < from)
  782.         ) {
  783.         dir->ccache.table[chi] = cc;
  784.         dir->ccache.table[from] = 0;
  785.         chi = from;
  786.     }
  787.     from = (from + 1) & mask;
  788.     }
  789. }
  790.  
  791. /* Shorten a cached character. */
  792. /* diff >= sizeof(cached_char_head). */
  793. private void
  794. shorten_cached_char(gs_font_dir * dir, cached_char * cc, uint diff)
  795. {
  796.     gx_bits_cache_shorten((gx_bits_cache *) & dir->ccache, &cc->head,
  797.               diff, cc->chunk);
  798.     if_debug2('K', "[K]shortening creates free block 0x%lx(%u)\n",
  799.           (ulong) ((byte *) cc + cc->head.size), diff);
  800. }
  801.